import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr={1,4,3,5,4,2,7,9,4,3,8};
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void countSort(int[] array){
        //求最大值和最小值
        int min=array[0];
        int max=array[0];
        for(int i=1;i<array.length;i++){
            if(min>array[i]){
                min=array[i];
            }
            if(max<array[i]){
                max=array[i];
            }
        }
        int len=max-min+1;
        int[] count=new int[len];
        //遍历原来数组，存放元素到计数数组中
        for(int i=0;i<array.length;i++){
            int index=array[i]-min;
            count[index]++;
        }
        //遍历记数数组
        int arrIndex=0;
        for(int i=0;i<count.length;i++){
            while(count[i]!=0){
                array[arrIndex]=i+min;
                arrIndex++;
                count[i]--;
            }
        }

    }
}